package algorithm.slidingWindow;

import java.util.LinkedList;

public class SlidingWindowMaxArray {
    /*
    *            -----------
    *     <-----|           |<------>
    *            -----------
    * */
    //滑动窗口：1、窗口的左右边界“不会回退”；2、判断滑动窗口双端队列是“最大值更新结构”还是“最小值更新结构”。
    //减少了重复的比较或计算

    //1、双端队列里存储下标，方便判断最左边的最大或最小值是否过期
    //2、向队列里加数据，相等的时候也要将双端队列里的数取出*****

    public static int[] getMaxWindow2(int[] arr, int w) {
        if (arr == null || w < 1 || arr.length < w) {
            return null;
        }
        // qmax 窗口最大值的更新结构
        // 放下标
        LinkedList<Integer> qmax = new LinkedList<>();
        int[] res = new int[arr.length - w + 1];
        int index = 0;
        for (int R = 0; R < arr.length; R++) {
            while (!qmax.isEmpty() && arr[qmax.peekLast()] <= arr[R]) {
                qmax.pollLast();
            }
            qmax.addLast(R);
            if (qmax.peekFirst() == R - w) {
                qmax.pollFirst();
            }
            if (R >= w - 1) {
                res[index++] = arr[qmax.peekFirst()];
            }
        }
        return res;
    }


    public static int[] getMaxWindow(int[] arr, int w){
        if(arr == null || w <= 0 || arr.length < w )
            return null;
        int[] res = new int[arr.length - w + 1];
        LinkedList<Integer> queue = new LinkedList<>();
        queue.addLast(0);
        for (int i = 1; i < w - 1; i++) {
            while(!queue.isEmpty() && arr[queue.peekLast()] < arr[i]){
                queue.pollLast();
            }
            queue.addLast(i);
        }

        int L = 0;
        int R = w - 1;
        for (int i = 0; i < res.length; i++, L++, R++){
            // 相等的时候也要将双端队列里的数取出，放进新的等值下标，相当于当前的这个数值的保质期变长了
            while(!queue.isEmpty() && arr[queue.peekLast()] <= arr[R]){
                queue.pollLast();
            }
            queue.addLast(R);
            Integer first = queue.peekFirst();
            if(first <= L){
                queue.pollFirst();
            }
            res[i] = arr[first];
        }
        return res;
    }

    public static void main(String[] args) {

    }
}
